package org.algorithm.熊猫.栈.第1周;


import org.junit.Test;

import java.util.Stack;

/**
 * @date 2022-04-06 星期三 00:00
 * 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek返回 -1。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
 */
public class 栈排序 {

    @Test
    public void test() {
        SortedStack stack = new SortedStack();
        stack.pop();
        stack.pop();
        stack.push(1);
        stack.pop();
        System.out.println(stack.peek());
       stack.pop();
        System.out.println(stack.peek());
    }

    class SortedStack {

        Stack<Integer> stack;
        Stack<Integer> temp;

        public SortedStack() {
            stack = new Stack<>();
            temp = new Stack<>();
        }

        public void push(int val) {
            if (!stack.isEmpty()) {
                while (!stack.isEmpty() && val > stack.peek()) {
                    temp.push(stack.pop());
                }
                stack.push(val);
                while (!temp.isEmpty()) {
                    stack.push(temp.pop());
                }
            } else {
                stack.push(val);
            }
        }

        public void pop() {
            if(!stack.isEmpty()){
                stack.pop();
            }
        }

        public int peek() {
            if(!stack.isEmpty()){
                return stack.peek();
            }
           return -1;
        }

        public boolean isEmpty() {
            return stack.isEmpty();
        }
    }
}
